#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

class DirectedAcyclicGraph {
private:
    int numVertices;  // 图的顶点数
    vector<vector<pair<int, int>>> adjacencyList;  // 邻接表表示的有向无环图

public:
    DirectedAcyclicGraph(int numVertices) : numVertices(numVertices) {
        adjacencyList.resize(numVertices);
    }
    void addEdge(int src, int dest, int weight) {
        adjacencyList[src].push_back(make_pair(dest, weight));  // 添加边，参数依次为源顶点、目标顶点、权重
    }
    vector<int> topologicalSort() const {
        vector<int> inDegree(numVertices, 0);  // 记录每个顶点的入度
        for (int src = 0; src < numVertices; ++src) {
            for (const auto& edge : adjacencyList[src]) {//循环计算每个点的入度
                int dest = edge.first;
                inDegree[dest]++;
            }
        }
        priority_queue<int, vector<int>, greater<int>> pq;  // 优先队列用于存储入度为0的顶点
        for (int vertex = 0; vertex < numVertices; ++vertex) {//将入度为0的点进入队列
            if (inDegree[vertex] == 0) {
                pq.push(vertex);
            }
        }
        vector<int> sortedOrder;  // 存储拓扑排序的结果
        while (!pq.empty()) {
            int currentVertex = pq.top();
            pq.pop();
            sortedOrder.push_back(currentVertex);//将出队列元素加入拓扑序中
            //cout<<currentVertex;
            for (const auto& edge : adjacencyList[currentVertex]) {
                int neighbor = edge.first;
                inDegree[neighbor]--;//出队列，并将这个点连的点的入度减一
                if (inDegree[neighbor] == 0) {//入度为0的点进入
                    pq.push(neighbor);
                }
            }
        }

        return sortedOrder;
    }

    vector<int> getCriticalPath() const {
        vector<int> sortedOrder = topologicalSort();  // 获取拓扑排序结果
        vector<int> earliestTime(numVertices, 0);  // 存储每个顶点的最早开始时间
        vector<int> latestTime(numVertices, numeric_limits<int>::max());  // 存储每个顶点的最晚开始时间

        // 计算每个顶点的最早开始时间
        for (int vertex : sortedOrder) {
            for (const auto& edge : adjacencyList[vertex]) {
                int neighbor = edge.first;
                int weight = edge.second;
                earliestTime[neighbor] = max(earliestTime[neighbor], earliestTime[vertex] + weight);
            }
        }

        latestTime[numVertices - 1] = earliestTime[numVertices - 1];
        // 计算每个顶点的最晚开始时间
        for (int i = numVertices - 2; i >= 0; --i) {
            int vertex = sortedOrder[i];
            for (const auto& edge : adjacencyList[vertex]) {
                int neighbor = edge.first;
                int weight = edge.second;
                latestTime[vertex] = min(latestTime[vertex], latestTime[neighbor] - weight);
            }
        }

        vector<int> criticalPath;  // 存储关键路径上的顶点
        // 找出关键路径上的顶点
        for (int vertex = 0; vertex < numVertices; ++vertex) {//如果最晚与最早时间相同，那么就为关键路径，不能耽误
            if (earliestTime[vertex] == latestTime[vertex]) {
                criticalPath.push_back(vertex);
            }
        }

        return criticalPath;
    }
};

